"""
给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
"""

"""
需要在执行到子节点的时候，再进行递归，用子节点做根节点,test2时候，把３算了两次,
"""
from leetcode_test import TreeNode


class Solution:
    count = 0
    def pathSum(self, root: TreeNode, sum: int) -> int:
        self.count += 1
        if not root:
            return 0
        ans = 0

        def helper(root, sum_) -> int:
            nonlocal ans
            if not root:
                return
            if sum_ == root.val:
                ans += 1

            helper(root.left, sum_ - root.val)
            helper(root.right, sum_ - root.val)
            return ans

        ans = helper(root, sum)
        ans += self.pathSum(root.left, sum)
        ans += self.pathSum(root.right, sum)

        return ans


def test():
    t = TreeNode.create([10, 5, -3, 3, 2, None, 11, 3, -2, None, 1])
    assert Solution().pathSum(t, 8) == 3


def test1():
    t = TreeNode.create([])
    assert Solution().pathSum(t, 8) == 0


def test2():
    t = TreeNode.create([1, None, 2, None, 3, None, 4, None, 5])
    assert Solution().pathSum(t, 3) == 2


if __name__ == "__main__":
    t = TreeNode.create([1, None, 2, None, 3, None, 4, None, 5])
    s = Solution()
    print(s.pathSum(t, 3))
    print(s.count)
